package com.zyk.grate_offer.class03;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 最长无重复字符子串
 *
 * @author zhangsan
 * @date 2021/4/28 9:09
 */
public class Code01_LongestSubStringWithoutRepeatingChar {

    // 窗口
    public static int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    // 0 <= s.length <= 5 * 104
    // s 由英文字母、数字、符号和空格组成
    // 动态规划
    public static int lengthOfLongestSubstring2(String s) {
        int N;
        if ((N = s.length()) == 0) return 0;
        char[] str = s.toCharArray();
        int[] map = new int[256];   // 上一个相同字符出现的位置。 或者说当前字符结束后把自己的位置放到里边去给下一个用
        Arrays.fill(map, -1);
        map[str[0]] = 0;
        int pre = 1;    // 以第0个结尾的答案为1
        int ans = 1;

        for (int i = 1; i < N; i++) {
            pre = Math.min(i - map[str[i]], pre + 1);
            ans = Math.max(pre, ans);
            map[str[i]] = i;
        }
        return ans;
    }


    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s));
        System.out.println(lengthOfLongestSubstring2(s));
    }

}
